#
# @lc app=leetcode.cn id=51 lang=python
#
# [51] N 皇后
#

# @lc code=start
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        self.n = n
        self.sub = ['.'*n for i in range(n)]
        self.result = []
        self.loop([[False] * n for _ in range(n)], 0)
        return self.result
    

    def loop(self, used, l):
        if l == self.n:
            self.result.append(self.sub[:])
            return
            
        for i in range(self.n):
            if used[l][i]:
                continue

            self.sub[l] = self.sub[l][:i] + 'Q' + self.sub[l][i+1:]
            new_used = [row[:] for row in used]
            cur = 1
            while cur+l < self.n:
                new_used[cur+l][i] = True
                if i-cur >= 0:
                    new_used[cur+l][i-cur] = True
                if i+cur < self.n:
                    new_used[cur+l][i+cur] = True
                cur += 1
            self.loop(new_used, l+1)

            self.sub[l] = self.sub[l][:i] + '.' + self.sub[l][i+1:]
            
        
# @lc code=end

